#pragma once

#include "../alloc.h"

namespace sfc::collections::list {

template <class T>
struct Node {
  Node* _next;
  Node* _prev;
  T _element;
};

template <class T>
struct Iter : iter::Iterator<Iter<T>, T&> {
  Node<T>* _node;

  [[sfc_inline]] auto next() -> Option<T&> {
    if (_node == nullptr) {
      return {};
    }
    const auto p = _node;
    _node = _node->_next;
    return *p;
  }

  [[sfc_inline]] auto prev() -> Option<T&> {
    if (_node == nullptr) {
      return {};
    }
    const auto p = _node;
    _node = _node->_prev;
    return *p;
  }
};

template <class T>
struct Cursor {
  Node<T>* _node;

  [[sfc_inline]] auto operator==(const Cursor& other) const -> bool {
    return _node == other._node;
  }

  [[sfc_inline]] auto operator*() const -> T& {
    return _node->_element;
  }

  [[sfc_inline]] auto operator++() -> Cursor& {
    _node = _node->_next;
    return *this;
  }
};

template <class T>
struct List {
  using Node = list::Node<T>;

  Node* _head;
  Node* _tail;
  usize _len;

  // head........tail
  List() : _head{nullptr}, _tail{nullptr}, _len{0} {}

  ~List() {
    this->clear();
  }

  auto len() const -> usize {
    return _len;
  }

  auto is_empty() const -> bool {
    return _head == nullptr;
  }

  void clear() {
    while (_head != nullptr) {
      auto p = Box<>::from_raw(_head);
      _head = _head->_next;
    }
  }

  auto front() const -> Option<const T&> {
    if (_head == nullptr) {
      return {};
    }
    return _head->_element;
  }

  auto front_mut() -> Option<T&> {
    if (_head == nullptr) {
      return {};
    }
    return _head->_element;
  }

  auto back() const -> Option<const T&> {
    if (_tail == nullptr) {
      return {};
    }
    return _head->_element;
  }

  auto back_mut() -> Option<T&> {
    if (_tail == nullptr) {
      return {};
    }
    return _head->_element;
  }

  void push_front(T ele) {
    auto p = Box<>::xnew(Node{_head, nullptr, mem::move(ele)}).into_raw();
    if (_head == nullptr) {
      _tail = p;
    } else {
      _head->_prev = p;
    }
    _head = p;
    _len += 1;
  }

  auto pop_front() -> Option<T> {
    if (_head == nullptr) {
      return {};
    }
    auto node = Box<>::from_raw(_head);
    _head = _head->_next;
    if (_head == nullptr) {
      _tail = nullptr;
    } else {
      _head->_prev = nullptr;
    }
    _len -= 1;
    return mem::move(*node);
  }

  void push_back(T ele) {
    auto p = Box<>::xnew(Node{nullptr, _tail, mem::move(ele)}).into_raw();
    if (_tail == nullptr) {
      _head = p;
    } else {
      _tail->_next = p;
    }
    _tail = p;
    _len += 1;
  }

  auto pop_back() -> Option<T> {
    if (_tail == nullptr) {
      return {};
    }
    auto node = Box<>::from_raw(_tail);
    _tail = _tail->_prev;
    if (_tail == nullptr) {
      _head = nullptr;
    } else {
      _tail->_next = nullptr;
    }
    _len -= 1;
    return mem::move(*node);
  }

  using Iter = list::Iter<const T>;
  auto iter() const -> Iter {
    return {reinterpret_cast<list::Node<const T>*>(_head)};
  }

  using IterMut = list::Iter<T>;
  auto iter_mut() -> IterMut {
    return {_head};
  }

  auto begin() const -> Cursor<const T> {
    return {reinterpret_cast<list::Node<const T>*>(_head)};
  }

  auto end() const -> Cursor<const T> {
    return {nullptr};
  }

  auto begin() -> Cursor<T> {
    return {_head};
  }

  auto end() -> Cursor<T> {
    return {nullptr};
  }

  template <class W>
  void format(fmt::Formatter<W>& f) const {
    auto b = f.box("[,]");
    for (auto&& x : *this) {
      b.entry(x);
    }
  }
};

}  // namespace sfc::collections::list
